package arithmetic.reverselist;

/**
 * 反转链表
 * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
 *
 * 进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
 */
public class Test {

    public static void main(String[] args) {

    }

    /**
     * head = [1,2,3,4,5]
     * 时间复杂度O(n)
     * 空间复杂度O(1)
     * @param head
     * @return
     */
    public static ListNode reverseList(ListNode head){
        ListNode preNode=null;
        ListNode cur=head;
        while (cur!=null){
            ListNode next=cur.next;
            cur.next=preNode;
            preNode=cur;
            cur=next;
        }
        return preNode;
    }

    /**
     * 递归
     * 时间复杂度O(n)
     * 空间复杂度O(n)
     * @param head
     * @return
     */
    public static ListNode reverseList1(ListNode head){
        if (head == null || head.next == null) return head;
        ListNode newHead=reverseList1(head.next);
        head.next.next=head;
        head.next=null;
        return newHead;
    }

}

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

